<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 5.1.1">
  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/oldimgs/32.ico">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/oldimgs/16.ico">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">

<link rel="stylesheet" href="/css/main.css">

<link rel="stylesheet" href="//fonts.googleapis.com/css?family=sans-serif:300,300italic,400,400italic,700,700italic|Ubuntu:300,300italic,400,400italic,700,700italic|Roboto:300,300italic,400,400italic,700,700italic|'Open+Sans':300,300italic,400,400italic,700,700italic|'Microsoft+YaHei':300,300italic,400,400italic,700,700italic|sans-serif;:300,300italic,400,400italic,700,700italic|Source+Code+Pro:300,300italic,400,400italic,700,700italic|monospace:300,300italic,400,400italic,700,700italic&display=swap&subset=latin,latin-ext">

<link rel="stylesheet" href="//cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free@5.14.0/css/all.min.css">
  <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/animate.css@3.1.1/animate.min.css">
  <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/pace-js@1.0.2/themes/blue/pace-theme-minimal.css">
  <script src="//cdn.jsdelivr.net/npm/pace-js@1.0.2/pace.min.js"></script>

<script class="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"http:/ShuYuMo2003.github.io","root":"/","scheme":"Mist","version":"8.0.0","exturl":false,"sidebar":{"position":"left","width":230,"display":"post","padding":18,"offset":12},"copycode":true,"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"搜索...","empty":"没有找到任何搜索结果：${query}","hits_time":"找到 ${hits} 个搜索结果（用时 ${time} 毫秒）","hits":"找到 ${hits} 个搜索结果"},"path":"search.xml","localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false}};
  </script>

  <meta name="description" content="CF505E Mr. Kitayuta vs. Bamboos 给定 $n$ 个数（竹子的高度） $h_{1 \dots n}$。 你需要进行 $m$ 轮操作，每轮操作为 $k$ 次修改，每次修改可以选择一个数 $h_i$ 修改为 $\max(h_i - p, 0)$（砸到地下）。 每轮操作后每个 $h_i$ 将会被修改为 $h_i + a_i$（每天竹子会生长）。 你需要最小化最终 $h_{1">
<meta property="og:type" content="article">
<meta property="og:title" content="「题单」IOI2020国家集训队作业 Part 1">
<meta property="og:url" content="2020/%E3%80%8C%E9%A2%98%E5%8D%95%E3%80%8DIOI2020%E5%9B%BD%E5%AE%B6%E9%9B%86%E8%AE%AD%E9%98%9F%E4%BD%9C%E4%B8%9A-Part-1/index.html">
<meta property="og:site_name" content="Shu Yu Mo&#39;s blog">
<meta property="og:description" content="CF505E Mr. Kitayuta vs. Bamboos 给定 $n$ 个数（竹子的高度） $h_{1 \dots n}$。 你需要进行 $m$ 轮操作，每轮操作为 $k$ 次修改，每次修改可以选择一个数 $h_i$ 修改为 $\max(h_i - p, 0)$（砸到地下）。 每轮操作后每个 $h_i$ 将会被修改为 $h_i + a_i$（每天竹子会生长）。 你需要最小化最终 $h_{1">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="2020-10-19T09:05:04.000Z">
<meta property="article:modified_time" content="2021-01-09T13:13:08.945Z">
<meta property="article:author" content="舒雨墨">
<meta property="article:tag" content="好题">
<meta property="article:tag" content="题解">
<meta name="twitter:card" content="summary">


<link rel="canonical" href="2020/「题单」IOI2020国家集训队作业-Part-1/">


<script data-pjax class="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true,
    lang   : 'zh-CN'
  };
</script>

  <title>「题单」IOI2020国家集训队作业 Part 1 | Shu Yu Mo's blog</title>
  






  <noscript>
  <style>
  body { margin-top: 2rem; }

  .use-motion .menu-item,
  .use-motion .sidebar,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header {
    visibility: visible;
  }

  .use-motion .header,
  .use-motion .site-brand-container .toggle,
  .use-motion .footer { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle,
  .use-motion .custom-logo-image {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line {
    transform: scaleX(1);
  }

  .search-pop-overlay, .sidebar-nav { display: none; }
  .sidebar-panel { display: block; }
  </style>
</noscript>

</head>

<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
  <div class="headband"></div>

  <main class="main">
    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏">
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <i class="logo-line"></i>
      <h1 class="site-title">Shu Yu Mo's blog</h1>
      <i class="logo-line"></i>
    </a>
      <p class="site-subtitle" itemprop="description">远行者</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>



<nav class="site-nav">
  <ul class="main-menu menu">
        <li class="menu-item menu-item-home">

    <a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a>

  </li>
        <li class="menu-item menu-item-about">

    <a href="/about/" rel="section"><i class="fa fa-user fa-fw"></i>关于</a>

  </li>
        <li class="menu-item menu-item-tags">

    <a href="/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>标签</a>

  </li>
        <li class="menu-item menu-item-links">

    <a href="/link/" rel="section"><i class="fa fa-th fa-fw"></i>links</a>

  </li>
        <li class="menu-item menu-item-archives">

    <a href="/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档</a>

  </li>
        <li class="menu-item menu-item-templates">

    <a href="/port/" rel="section"><i class="fa fa-heartbeat fa-fw"></i>Templates</a>

  </li>
        <li class="menu-item menu-item-latex">

    <a href="/LaTeX-syntax.html" rel="section"><i class="fa fa-heartbeat fa-fw"></i>LaTeX</a>

  </li>
        <li class="menu-item menu-item-sitemap">

    <a href="/sitemap.xml" rel="section"><i class="fa fa-sitemap fa-fw"></i>站点地图</a>

  </li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off" maxlength="80"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div class="search-result-container no-result">
  <div class="search-result-icon">
    <i class="fa fa-spinner fa-pulse fa-5x"></i>
  </div>
</div>

    </div>
  </div>

</div>
        
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
  </div>

  <aside class="sidebar">

    <div class="sidebar-inner sidebar-nav-active sidebar-toc-active">
      <ul class="sidebar-nav" style="display:none;">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <section class="post-toc-wrap sidebar-panel">

        <div class="site-author animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="舒雨墨"
      src="/images/avatar.jpg">
  <p class="site-author-name" itemprop="name">舒雨墨</p>
  <div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/archives/">
        
          <span class="site-state-item-count">106</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
        <span class="site-state-item-count">28</span>
        <span class="site-state-item-name">分类</span>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/tags/">
          
        <span class="site-state-item-count">53</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author animated">
      <span class="links-of-author-item">
        <a href="https://github.com/ShuYuMo2003" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;ShuYuMo2003" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://www.luogu.com.cn/user/44615" title="Luogu → https:&#x2F;&#x2F;www.luogu.com.cn&#x2F;user&#x2F;44615" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>Luogu</a>
      </span>
      <span class="links-of-author-item">
        <a href="mailto:sujiayi2003@gmail.com" title="E-Mail → mailto:sujiayi2003@gmail.com" rel="noopener" target="_blank"><i class="fa fa-envelope fa-fw"></i>E-Mail</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://twitter.com/JiaYiSu5" title="Twitter → https:&#x2F;&#x2F;twitter.com&#x2F;JiaYiSu5" rel="noopener" target="_blank"><i class="fab fa-twitter fa-fw"></i>Twitter</a>
      </span>
  </div>



        <hr/>
          <div class="post-toc animated"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#CF505E-Mr-Kitayuta-vs-Bamboos"><span class="nav-number">1.</span> <span class="nav-text">CF505E Mr. Kitayuta vs. Bamboos</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#code"><span class="nav-number">1.1.</span> <span class="nav-text">code</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#CF521D-Shop"><span class="nav-number">2.</span> <span class="nav-text">CF521D Shop</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#code-1"><span class="nav-number">2.1.</span> <span class="nav-text">code</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#CF526F-Pudding-Monsters"><span class="nav-number">3.</span> <span class="nav-text">CF526F Pudding Monsters</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#code-2"><span class="nav-number">3.1.</span> <span class="nav-text">code</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#CF521E-Cycling-City"><span class="nav-number">4.</span> <span class="nav-text">CF521E Cycling City</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#CF547D-Mike-and-Fish"><span class="nav-number">5.</span> <span class="nav-text">CF547D Mike and Fish</span></a></li></ol></div>
      </section>
      <!--/noindex-->

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-author animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="舒雨墨"
      src="/images/avatar.jpg">
  <p class="site-author-name" itemprop="name">舒雨墨</p>
  <div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/archives/">
        
          <span class="site-state-item-count">106</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
        <span class="site-state-item-count">28</span>
        <span class="site-state-item-name">分类</span>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/tags/">
          
        <span class="site-state-item-count">53</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author animated">
      <span class="links-of-author-item">
        <a href="https://github.com/ShuYuMo2003" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;ShuYuMo2003" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://www.luogu.com.cn/user/44615" title="Luogu → https:&#x2F;&#x2F;www.luogu.com.cn&#x2F;user&#x2F;44615" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>Luogu</a>
      </span>
      <span class="links-of-author-item">
        <a href="mailto:sujiayi2003@gmail.com" title="E-Mail → mailto:sujiayi2003@gmail.com" rel="noopener" target="_blank"><i class="fa fa-envelope fa-fw"></i>E-Mail</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://twitter.com/JiaYiSu5" title="Twitter → https:&#x2F;&#x2F;twitter.com&#x2F;JiaYiSu5" rel="noopener" target="_blank"><i class="fab fa-twitter fa-fw"></i>Twitter</a>
      </span>
  </div>



      </section>
    </div>
  </aside>
  <div class="sidebar-dimmer"></div>


    </header>

    
  <div class="back-to-top">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>

<noscript>
  <div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>


    <div class="main-inner post posts-expand">
      

      

    
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="/2020/「题单」IOI2020国家集训队作业-Part-1/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.jpg">
      <meta itemprop="name" content="舒雨墨">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Shu Yu Mo's blog">
    </span>

    
    
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          「题单」IOI2020国家集训队作业 Part 1
        </h1>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2020-10-19 17:05:04" itemprop="dateCreated datePublished" datetime="2020-10-19T17:05:04+08:00">2020-10-19</time>
    </span>
      <span class="post-meta-item">
        <span class="post-meta-item-icon">
          <i class="far fa-calendar-check"></i>
        </span>
        <span class="post-meta-item-text">更新于</span>
        <time title="修改时间：2021-01-09 21:13:08" itemprop="dateModified" datetime="2021-01-09T21:13:08+08:00">2021-01-09</time>
      </span>

  
    <span id="2020/「题单」IOI2020国家集训队作业-Part-1/" class="post-meta-item leancloud_visitors" data-flag-title="「题单」IOI2020国家集训队作业 Part 1" title="阅读次数">
      <span class="post-meta-item-icon">
        <i class="far fa-eye"></i>
      </span>
      <span class="post-meta-item-text">阅读次数：</span>
      <span class="leancloud-visitors-count"></span>
    </span>
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Valine：</span>
    
    <a title="valine" href="/2020/「题单」IOI2020国家集训队作业-Part-1/#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="2020/「题单」IOI2020国家集训队作业-Part-1/" itemprop="commentCount"></span>
    </a>
  </span>
  
  
      </div>
      <div class="post-meta">
    <span class="post-meta-item" title="本文字数">
      <span class="post-meta-item-icon">
        <i class="far fa-file-word"></i>
      </span>
      <span class="post-meta-item-text">本文字数：</span>
      <span>13k</span>
    </span>
    <span class="post-meta-item" title="阅读时长">
      <span class="post-meta-item-icon">
        <i class="far fa-clock"></i>
      </span>
      <span class="post-meta-item-text">阅读时长 &asymp;</span>
      <span>12 分钟</span>
    </span>
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
        <h1 id="CF505E-Mr-Kitayuta-vs-Bamboos"><a href="#CF505E-Mr-Kitayuta-vs-Bamboos" class="headerlink" title="CF505E Mr. Kitayuta vs. Bamboos"></a>CF505E Mr. Kitayuta vs. Bamboos</h1><ul>
<li>给定 $n$ 个数（竹子的高度） $h_{1 \dots n}$。</li>
<li>你需要进行 $m$ 轮操作，每轮操作为 $k$ 次修改，每次修改可以选择一个数 $h_i$ 修改为 $\max(h_i - p, 0)$（砸到地下）。</li>
<li>每轮操作后每个 $h_i$ 将会被修改为 $h_i + a_i$（每天竹子会生长）。</li>
<li>你需要最小化最终 $h_{1 \dots n}$ 中的最大值。</li>
<li>$n \le 10^5$，$m \le 5 \times 10^3$，$k \le 10$<a id="more"></a>
要求最小化最大值，考虑二分一个最大的高度，将问题转化成可行性问题，即，给出一个高度，问能否使这些竹子最终不超过这个高度。</li>
</ul>
<p>考虑限制这个问题不平凡的因素：因为每次降低竹子高度的时候不能保证竹子一定降低 p ，也就是说，“砸竹子”这一动作存在浪费。我们考虑尽可能的让“砸竹子”这一动作更少的浪费，即：尽可能在后面的时间点砸竹子，但是无法保证到底是在哪一次砸竹子，有可能已经结束了，没有形式化的计算流程。</p>
<p>可以考虑反向思考，即：假设已经长到 二分的高度。每次生长操作相当于每次会下落 $a_i$，而每次砸的操作相当于提升了 $p$ 的高度。</p>
<p>开始时，对每一个竹子计算出其需要多少次会下落到负高度，用堆维护，每次取出最快的可能下落到负高度的 k 个竹子，进行 “拔高” 操作。然后判断最后的高度是否大于等于$h_i$。</p>
<p>其实二分的本质是为了确定“尽可能的靠后砸竹子”的标准。反向思考是为了便于贪心处理策略。</p>
<h2 id="code"><a href="#code" class="headerlink" title="code"></a>code</h2><details class="note info"><summary><p>CF505E Mr. Kitayuta vs. Bamboos</p>
</summary>
<pre class="line-numbers language-cpp" data-language="cpp"><code class="language-cpp"><span class="token keyword">int</span> n<span class="token punctuation">,</span> m<span class="token punctuation">,</span> k<span class="token punctuation">,</span> p<span class="token punctuation">;</span>
<span class="token keyword">int</span> H<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">,</span> A<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token expression">mp make_pair</span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token expression">fi first</span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token expression">se second</span></span>
<span class="token keyword">int</span> height<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">bool</span> <span class="token function">check</span><span class="token punctuation">(</span><span class="token keyword">int</span> MaxH<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
	<span class="token function">fill</span><span class="token punctuation">(</span>height <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> height <span class="token operator">+</span> <span class="token number">1</span> <span class="token operator">+</span> n<span class="token punctuation">,</span> MaxH<span class="token punctuation">)</span><span class="token punctuation">;</span>
	priority_queue<span class="token operator">&lt;</span>pair<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token operator">></span><span class="token punctuation">,</span> vector<span class="token operator">&lt;</span>pair<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token operator">></span> <span class="token operator">></span> <span class="token punctuation">,</span> greater<span class="token operator">&lt;</span>pair<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token operator">></span> <span class="token operator">></span> <span class="token operator">></span> Q<span class="token punctuation">;</span>
	<span class="token keyword">while</span><span class="token punctuation">(</span><span class="token operator">!</span>Q<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> Q<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token keyword">if</span><span class="token punctuation">(</span>MaxH <span class="token operator">-</span> m <span class="token operator">*</span> A<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">&lt;</span> H<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> Q<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token function">mp</span><span class="token punctuation">(</span> MaxH <span class="token operator">/</span> A<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> i <span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> m<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
		<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> j <span class="token operator">&lt;=</span> k<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
			<span class="token keyword">if</span><span class="token punctuation">(</span>Q<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
			pair<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token operator">></span> now <span class="token operator">=</span> Q<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> Q<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> 
			<span class="token keyword">if</span><span class="token punctuation">(</span>now<span class="token punctuation">.</span>fi <span class="token operator">&lt;</span> i<span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
			height<span class="token punctuation">[</span>now<span class="token punctuation">.</span>se<span class="token punctuation">]</span> <span class="token operator">+=</span> p<span class="token punctuation">;</span>
			now<span class="token punctuation">.</span>fi <span class="token operator">=</span> height<span class="token punctuation">[</span>now<span class="token punctuation">.</span>se<span class="token punctuation">]</span> <span class="token operator">/</span> A<span class="token punctuation">[</span>now<span class="token punctuation">.</span>se<span class="token punctuation">]</span><span class="token punctuation">;</span>
			<span class="token keyword">if</span><span class="token punctuation">(</span>height<span class="token punctuation">[</span>now<span class="token punctuation">.</span>se<span class="token punctuation">]</span> <span class="token operator">-</span> m <span class="token operator">*</span> A<span class="token punctuation">[</span>now<span class="token punctuation">.</span>se<span class="token punctuation">]</span> <span class="token operator">&lt;</span> H<span class="token punctuation">[</span>now<span class="token punctuation">.</span>se<span class="token punctuation">]</span><span class="token punctuation">)</span> Q<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>now<span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token punctuation">&#125;</span>
	<span class="token punctuation">&#125;</span>
	<span class="token keyword">return</span> Q<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">signed</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
	n <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> m <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> k <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> p <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 竹子数 天数 修改次数 最大降低高度 </span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> H<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> A<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

	<span class="token keyword">int</span> L <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span> ans <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span> R <span class="token operator">=</span> <span class="token number">1LL</span> <span class="token operator">&lt;&lt;</span> <span class="token number">60</span><span class="token punctuation">;</span> <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> L <span class="token operator">=</span> <span class="token function">min</span><span class="token punctuation">(</span>L<span class="token punctuation">,</span> A<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">while</span><span class="token punctuation">(</span>L <span class="token operator">&lt;</span> R<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
		<span class="token keyword">int</span> mid <span class="token operator">=</span> <span class="token punctuation">(</span>L <span class="token operator">+</span> R<span class="token punctuation">)</span> <span class="token operator">>></span> <span class="token number">1</span><span class="token punctuation">;</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span><span class="token function">check</span><span class="token punctuation">(</span>mid<span class="token punctuation">)</span><span class="token punctuation">)</span> ans <span class="token operator">=</span> mid<span class="token punctuation">,</span> R <span class="token operator">=</span> mid<span class="token punctuation">;</span>
		<span class="token keyword">else</span> L <span class="token operator">=</span> mid <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span>
	<span class="token punctuation">&#125;</span>
	<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%lld\n"</span><span class="token punctuation">,</span> ans<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
</details>


<h1 id="CF521D-Shop"><a href="#CF521D-Shop" class="headerlink" title="CF521D Shop"></a>CF521D Shop</h1><ul>
<li>有 $k$ 个正整数 $a_{1\dots k}$。</li>
<li>有 $n$ 个操作，每个操作给定正整数 $b$，有三种可能：将 $a_i$ 赋值为 $b$，将 $a_i$ 加上 $b$，将 $a_i$ 乘以 $b$。</li>
<li>你可以从 $n$ 个操作中选择最多 $m$ 个操作，并按照一定顺序执行。</li>
<li>你的目标是最大化 $\prod_{i=1}^k a_i$ 的值。</li>
<li>$k,n \le 10^5$。</li>
</ul>
<p>化归思想，考虑如果只有乘法，那一定是把操作数字从大到小排序，然后以此操作。</p>
<p>考虑操作顺序，最优的操作一定是先赋值，再加法，最后乘法。其中赋值只可能选相应位置最大的赋值，加法也是从大到小考虑。</p>
<p>显然赋值可以直接转化成加法，而加法如果从大到小考虑也可以直接转化成乘法（乘一个实数）。</p>
<p>这样就把所有操作转化成了乘法。 贪心考虑即可。</p>
<p>最后输出有顺序，应按照上面的策略（先赋值，再加法，最后乘法）以此输出（操作顺序）。</p>
<h2 id="code-1"><a href="#code-1" class="headerlink" title="code"></a>code</h2><details class="note info"><summary><p>CF521D Shop</p>
</summary>
<pre class="line-numbers language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;climits></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstring></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cmath></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;algorithm></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;vector></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>
<span class="token keyword">const</span> <span class="token keyword">int</span> _ <span class="token operator">=</span> <span class="token number">1e5</span> <span class="token operator">+</span> <span class="token number">100</span><span class="token punctuation">;</span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token expression">LL <span class="token keyword">long</span> <span class="token keyword">long</span></span></span>
<span class="token keyword">int</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token keyword">int</span> x<span class="token punctuation">;</span> <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d"</span><span class="token punctuation">,</span> <span class="token operator">&amp;</span>x<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">return</span> x<span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
<span class="token keyword">int</span> n<span class="token punctuation">,</span> m<span class="token punctuation">,</span> k<span class="token punctuation">;</span>
<span class="token keyword">int</span> v<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">;</span>
pair<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token operator">></span> Give<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">;</span>
vector<span class="token operator">&lt;</span>pair<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token punctuation">,</span> <span class="token keyword">int</span> <span class="token operator">></span> <span class="token operator">></span> add<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">;</span>
vector<span class="token operator">&lt;</span>pair<span class="token operator">&lt;</span><span class="token keyword">double</span><span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token operator">></span> <span class="token operator">></span> mul<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">;</span>
vector<span class="token operator">&lt;</span>pair<span class="token operator">&lt;</span><span class="token keyword">double</span><span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token operator">></span> <span class="token operator">></span> All<span class="token punctuation">;</span>
<span class="token keyword">int</span> T<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> id<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token expression"><span class="token keyword">double</span> <span class="token keyword">long</span> <span class="token keyword">double</span></span></span>
<span class="token keyword">bool</span> <span class="token function">ICMP</span>  <span class="token punctuation">(</span><span class="token keyword">const</span> pair<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token operator">></span> <span class="token operator">&amp;</span> x<span class="token punctuation">,</span> <span class="token keyword">const</span> pair<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token operator">></span> <span class="token operator">&amp;</span> y<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token keyword">return</span> <span class="token punctuation">(</span>x <span class="token operator">></span> y<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
<span class="token keyword">bool</span> <span class="token function">ICMP_D</span><span class="token punctuation">(</span><span class="token keyword">const</span> pair<span class="token operator">&lt;</span><span class="token keyword">double</span><span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token operator">></span> <span class="token operator">&amp;</span> x<span class="token punctuation">,</span> <span class="token keyword">const</span> pair<span class="token operator">&lt;</span><span class="token keyword">double</span><span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token operator">></span> <span class="token operator">&amp;</span> y<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token keyword">return</span> <span class="token punctuation">(</span>x <span class="token operator">></span> y<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
<span class="token keyword">bool</span> <span class="token function">MAGIC</span><span class="token punctuation">(</span><span class="token keyword">const</span> <span class="token keyword">int</span> <span class="token operator">&amp;</span>x<span class="token punctuation">,</span> <span class="token keyword">const</span> <span class="token keyword">int</span> <span class="token operator">&amp;</span>y<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token keyword">return</span> T<span class="token punctuation">[</span>x<span class="token punctuation">]</span> <span class="token operator">&lt;</span> T<span class="token punctuation">[</span>y<span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
	k <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> n <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> m <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> k<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> v<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
		<span class="token keyword">int</span> type <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> T<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> type<span class="token punctuation">;</span>
		<span class="token keyword">int</span> a <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> b <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span>type <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
			Give<span class="token punctuation">[</span>a<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">max</span><span class="token punctuation">(</span>Give<span class="token punctuation">[</span>a<span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token function">make_pair</span><span class="token punctuation">(</span>b<span class="token punctuation">,</span> i<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span> 
		<span class="token punctuation">&#125;</span> <span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span>type <span class="token operator">==</span> <span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
			add<span class="token punctuation">[</span>a<span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span><span class="token function">make_pair</span><span class="token punctuation">(</span>b<span class="token punctuation">,</span> i<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token punctuation">&#125;</span> <span class="token keyword">else</span> <span class="token punctuation">&#123;</span>
			mul<span class="token punctuation">[</span>a<span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span><span class="token function">make_pair</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token keyword">double</span><span class="token punctuation">)</span><span class="token punctuation">(</span>b<span class="token punctuation">)</span><span class="token punctuation">,</span> i<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token punctuation">&#125;</span>
	<span class="token punctuation">&#125;</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> k<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span>Give<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>first<span class="token punctuation">)</span>
			add<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span><span class="token function">make_pair</span><span class="token punctuation">(</span>Give<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>first <span class="token operator">-</span> v<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> Give<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>second<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> k<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token function">sort</span><span class="token punctuation">(</span>add<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> add<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> ICMP<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> k<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
		LL now <span class="token operator">=</span> v<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
		<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> add<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
			mul<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span> 
				<span class="token function">make_pair</span><span class="token punctuation">(</span> 
					<span class="token punctuation">(</span><span class="token keyword">double</span><span class="token punctuation">)</span><span class="token punctuation">(</span>now <span class="token operator">+</span><span class="token number">0ll</span><span class="token operator">+</span> add<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">.</span>first<span class="token punctuation">)</span> <span class="token operator">/</span> <span class="token punctuation">(</span><span class="token keyword">double</span><span class="token punctuation">)</span><span class="token punctuation">(</span>now<span class="token punctuation">)</span><span class="token punctuation">,</span>
					add<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">.</span>second
				<span class="token punctuation">)</span> 
			<span class="token punctuation">)</span><span class="token punctuation">;</span> now <span class="token operator">+=</span> add<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">.</span>first<span class="token punctuation">;</span>
		<span class="token punctuation">&#125;</span>
	<span class="token punctuation">&#125;</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> k<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> mul<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span> All<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span>mul<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token function">sort</span><span class="token punctuation">(</span>All<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> All<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> ICMP_D<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">int</span> tot <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> All<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token keyword">if</span><span class="token punctuation">(</span>All<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>first <span class="token operator">></span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> tot<span class="token operator">++</span><span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
	tot <span class="token operator">=</span> <span class="token function">min</span><span class="token punctuation">(</span>tot<span class="token punctuation">,</span> m<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> tot<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> id<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> All<span class="token punctuation">[</span>i <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">.</span>second<span class="token punctuation">;</span>
	<span class="token function">sort</span><span class="token punctuation">(</span>id <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> id <span class="token operator">+</span> <span class="token number">1</span> <span class="token operator">+</span> tot<span class="token punctuation">,</span> MAGIC<span class="token punctuation">)</span><span class="token punctuation">;</span>	<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%d\n"</span><span class="token punctuation">,</span> tot<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> tot<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%d%c"</span><span class="token punctuation">,</span> id<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token string">" \n"</span><span class="token punctuation">[</span>i <span class="token operator">==</span> n<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
</details>

<h1 id="CF526F-Pudding-Monsters"><a href="#CF526F-Pudding-Monsters" class="headerlink" title="CF526F Pudding Monsters"></a>CF526F Pudding Monsters</h1><ul>
<li>给定一个 $n \times n$ 的棋盘，其中有 $n$ 个棋子，每行每列恰好有一个棋子。</li>
<li>求有多少个 $k \times k$ 的子棋盘中恰好有 $k$ 个棋子。</li>
<li>$n \le 3 \times 10^5$。</li>
</ul>
<p>每行每列<strong>恰好有一个</strong>棋子的棋盘，可以抽象成一个排列。 而操作也是对于一个排列的一段进行操作的。</p>
<p>题意可以转化为：</p>
<ul>
<li>给出一个排列</li>
<li>求连续段数量，即连续的一段，且段中的元素排好序之后必须是公差为$1$的等差数列.</li>
</ul>
<p><strong>连续段计数</strong></p>
<p>考虑如何刻画“<strong>连续的一段，且段中的元素排好序之后必须是公差为$1$的等差数列</strong>”这个条件，可以形式化的定义：</p>
<p>$$\operatorname{MaxVal} - \operatorname{MinVal} = (R - L)$$</p>
<p>即</p>
<p>$$f_{R}(L) = \operatorname{MaxVal} - \operatorname{MinVal} - (R - L) = 0$$</p>
<p>这个条件成立的基础在于，所求数列不能有重复元素，而且也保证了函数$f_x(L) \ge 0$, 查询时只需要维护<strong>最小值</strong>以及最小值的<strong>数量</strong>即可。</p>
<p>可以考虑枚举一个端点，比如右端点 $R$，然后查找有多少符合条件的左端点 $L$ ，用线段树维护$f_R(x)$在每个点处的函数值。</p>
<p>考虑当$f_x(L)$ 移动到 $f_{x + 1}(L)$ 时， 值的变化。变化的值有 $R$ , 可能变化的有$MaxVal, MinVal$。用单调栈实时维护更新后会波及哪些元素的最小值。事实上，单调栈处理的过程就是在动态维护一个后缀最小\大值数组。</p>
<p>这里有几个与其有相似之处的题目，但是可能做法并不一样，遇到不要想成一样的题目：</p>
<ul>
<li><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P5278">算术天才⑨与等差数列</a> (不保证序列中一定元素不重复)<ul>
<li>考虑判断一个序列排好序后是否为等差数列<ul>
<li>准确做法<ul>
<li>$\max−\min=(r−l)k$</li>
<li>相邻两数差的绝对值的 $\operatorname{gcd}$是 $k$</li>
<li>区间 $[l,r]$ 内的数不重复</li>
</ul>
</li>
<li>概率性做法<ul>
<li>hash思想，维护 $n$ 次方和</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
<li><a target="_blank" rel="noopener" href="http://www.zhengruioi.com/contest/718/problem/1615">树上排列(ZROI)</a>  (同样不保证元素一定不重复) <ul>
<li>给定一颗 $n$ 个点的树。每个点都一个正整数点权 $A_i$ ，你需要支持以下两种操作：</li>
<li>1、询问点 $x$ 和点 $y$ 之间的路径上的所有点（包括点 $x$ 和点 $y$ ）的点权是否构成一个从 $1$ 开始的排列（即若这条链长度为 $len$ ，那么问点权集合为 ${1,2,⋯,len}$ ）。</li>
<li>2、将 $A_x$ 修改为 $y$ 。</li>
<li>由于在树上难以判断某区间内的数字不重复，Hash维护n次方和。</li>
</ul>
</li>
<li>给出一个没有重复元素的序列，询问某区间中的元素是否能加入小于$k$个元素使其拍好序后构成一个等差数列。<ul>
<li>条件变成了 $$f_{R}(L) = \operatorname{MaxVal} - \operatorname{MinVal} - (R - L) \ge k$$</li>
</ul>
</li>
<li><a target="_blank" rel="noopener" href="http://www.zhengruioi.com/problem/1532">count(ZROI)</a>已知一个集合$S$中的最大元素为 $N$， 且这个集合中的元素可以构成一个等差数列，给出一些形如$x \in S$、$x \notin S$的限制。求最终的集合有多少种情况。<ul>
<li>考虑刻画一个等差数列需要什么参数：公差，和每个元素$\bmod $ 公差的值。枚举这两个参数，依次计数即可。</li>
</ul>
</li>
</ul>
<p>（引用正睿的两道题目，不知道是不是有版权问题，如果有，会立即删除（<del>顺便给正睿OI打个广告</del>））。</p>
<h2 id="code-2"><a href="#code-2" class="headerlink" title="code"></a>code</h2><details class="note info"><summary><p>CF526F Pudding Monsters</p>
</summary>
<pre class="line-numbers language-cpp" data-language="cpp"><code class="language-cpp"><span class="token keyword">int</span> n<span class="token punctuation">;</span>
<span class="token keyword">int</span> A<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token expression">fir first</span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token expression">sec second</span></span>
<span class="token keyword">namespace</span> SegmentTree<span class="token punctuation">&#123;</span>
    <span class="token keyword">const</span> <span class="token keyword">int</span> _ <span class="token operator">=</span> <span class="token number">3e6</span> <span class="token operator">+</span> <span class="token number">100</span><span class="token punctuation">;</span>
    <span class="token keyword">struct</span> <span class="token class-name">Node</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">int</span> MIN<span class="token punctuation">;</span>
        <span class="token keyword">int</span> sMIN<span class="token punctuation">;</span>
        <span class="token keyword">int</span> tar<span class="token punctuation">;</span>
        Node <span class="token keyword">operator</span> <span class="token operator">+</span> <span class="token punctuation">(</span><span class="token keyword">const</span> Node <span class="token operator">&amp;</span> rhs<span class="token punctuation">)</span> <span class="token keyword">const</span> <span class="token punctuation">&#123;</span>
            Node res<span class="token punctuation">;</span>
            res<span class="token punctuation">.</span>MIN  <span class="token operator">=</span> <span class="token function">min</span><span class="token punctuation">(</span>MIN<span class="token punctuation">,</span> rhs<span class="token punctuation">.</span>MIN<span class="token punctuation">)</span><span class="token punctuation">;</span>
            res<span class="token punctuation">.</span>sMIN <span class="token operator">=</span> MIN <span class="token operator">==</span> rhs<span class="token punctuation">.</span>MIN <span class="token operator">?</span> <span class="token punctuation">(</span> sMIN <span class="token operator">+</span> rhs<span class="token punctuation">.</span>sMIN<span class="token punctuation">)</span> <span class="token operator">:</span> <span class="token punctuation">(</span>MIN <span class="token operator">&lt;</span> rhs<span class="token punctuation">.</span>MIN <span class="token operator">?</span> sMIN <span class="token operator">:</span> rhs<span class="token punctuation">.</span>sMIN<span class="token punctuation">)</span> <span class="token punctuation">;</span>
            <span class="token keyword">return</span> res<span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>v<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token keyword">int</span> tot <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token keyword">int</span> ch<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token expression"><span class="token function">ls</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span> <span class="token punctuation">(</span>ch<span class="token punctuation">[</span>o<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span></span></span>
    <span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token expression"><span class="token function">rs</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span> <span class="token punctuation">(</span>ch<span class="token punctuation">[</span>o<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span></span></span>
    <span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token expression"><span class="token function">make</span> <span class="token punctuation">(</span>tot<span class="token operator">++</span><span class="token punctuation">,</span> ch<span class="token punctuation">[</span>tot<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> ch<span class="token punctuation">[</span>tot<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> v<span class="token punctuation">[</span>tot<span class="token punctuation">]</span><span class="token punctuation">.</span>MIN <span class="token operator">=</span> v<span class="token punctuation">[</span>tot<span class="token punctuation">]</span><span class="token punctuation">.</span>sMIN <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span> tot<span class="token punctuation">)</span></span></span>
    <span class="token keyword">int</span> <span class="token function">Groot</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token keyword">return</span> make<span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
    <span class="token keyword">void</span> <span class="token function">maintain</span><span class="token punctuation">(</span><span class="token keyword">int</span> o<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
        v<span class="token punctuation">[</span>o<span class="token punctuation">]</span><span class="token punctuation">.</span>MIN  <span class="token operator">=</span> <span class="token function">min</span><span class="token punctuation">(</span>v<span class="token punctuation">[</span><span class="token function">ls</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span><span class="token punctuation">]</span><span class="token punctuation">.</span>MIN<span class="token punctuation">,</span> v<span class="token punctuation">[</span><span class="token function">rs</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span><span class="token punctuation">]</span><span class="token punctuation">.</span>MIN<span class="token punctuation">)</span><span class="token punctuation">;</span>
        v<span class="token punctuation">[</span>o<span class="token punctuation">]</span><span class="token punctuation">.</span>sMIN <span class="token operator">=</span> v<span class="token punctuation">[</span><span class="token function">ls</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span><span class="token punctuation">]</span><span class="token punctuation">.</span>MIN <span class="token operator">==</span> v<span class="token punctuation">[</span><span class="token function">rs</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span><span class="token punctuation">]</span><span class="token punctuation">.</span>MIN <span class="token operator">?</span> v<span class="token punctuation">[</span><span class="token function">ls</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span><span class="token punctuation">]</span><span class="token punctuation">.</span>sMIN <span class="token operator">+</span> v<span class="token punctuation">[</span><span class="token function">rs</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span><span class="token punctuation">]</span><span class="token punctuation">.</span>sMIN <span class="token operator">:</span> <span class="token punctuation">(</span> v<span class="token punctuation">[</span><span class="token function">ls</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span><span class="token punctuation">]</span><span class="token punctuation">.</span>MIN <span class="token operator">&lt;</span> v<span class="token punctuation">[</span><span class="token function">rs</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span><span class="token punctuation">]</span><span class="token punctuation">.</span>MIN <span class="token operator">?</span> v<span class="token punctuation">[</span><span class="token function">ls</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span><span class="token punctuation">]</span><span class="token punctuation">.</span>sMIN <span class="token operator">:</span> v<span class="token punctuation">[</span><span class="token function">rs</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span><span class="token punctuation">]</span><span class="token punctuation">.</span>sMIN <span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">void</span> <span class="token function">tar</span><span class="token punctuation">(</span><span class="token keyword">int</span> o<span class="token punctuation">,</span> <span class="token keyword">int</span> x<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> v<span class="token punctuation">[</span>o<span class="token punctuation">]</span><span class="token punctuation">.</span>MIN <span class="token operator">+=</span> x<span class="token punctuation">;</span> v<span class="token punctuation">[</span>o<span class="token punctuation">]</span><span class="token punctuation">.</span>tar <span class="token operator">+=</span> x<span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
    <span class="token keyword">void</span> <span class="token function">pushdown</span><span class="token punctuation">(</span><span class="token keyword">int</span> o<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>v<span class="token punctuation">[</span>o<span class="token punctuation">]</span><span class="token punctuation">.</span>tar<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token function">tar</span><span class="token punctuation">(</span><span class="token function">ls</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span><span class="token punctuation">,</span> v<span class="token punctuation">[</span>o<span class="token punctuation">]</span><span class="token punctuation">.</span>tar<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token function">tar</span><span class="token punctuation">(</span><span class="token function">rs</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span><span class="token punctuation">,</span> v<span class="token punctuation">[</span>o<span class="token punctuation">]</span><span class="token punctuation">.</span>tar<span class="token punctuation">)</span><span class="token punctuation">;</span>
            v<span class="token punctuation">[</span>o<span class="token punctuation">]</span><span class="token punctuation">.</span>tar <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">void</span> <span class="token function">build</span><span class="token punctuation">(</span><span class="token keyword">int</span> o<span class="token punctuation">,</span> <span class="token keyword">int</span> L<span class="token punctuation">,</span> <span class="token keyword">int</span> R<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>L <span class="token operator">==</span> R<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> v<span class="token punctuation">[</span>o<span class="token punctuation">]</span><span class="token punctuation">.</span>MIN <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> v<span class="token punctuation">[</span>o<span class="token punctuation">]</span><span class="token punctuation">.</span>sMIN <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token keyword">return</span><span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
        <span class="token keyword">int</span> mid <span class="token operator">=</span> <span class="token punctuation">(</span>L <span class="token operator">+</span> R<span class="token punctuation">)</span> <span class="token operator">>></span> <span class="token number">1</span><span class="token punctuation">;</span>
        <span class="token function">ls</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span> <span class="token operator">=</span> make<span class="token punctuation">;</span> <span class="token function">rs</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span> <span class="token operator">=</span> make<span class="token punctuation">;</span>
        <span class="token function">build</span><span class="token punctuation">(</span><span class="token function">ls</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span><span class="token punctuation">,</span> L<span class="token punctuation">,</span> mid<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token function">build</span><span class="token punctuation">(</span><span class="token function">rs</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span><span class="token punctuation">,</span> mid <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> R<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">maintain</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">void</span> <span class="token function">update</span><span class="token punctuation">(</span><span class="token keyword">int</span> o<span class="token punctuation">,</span> <span class="token keyword">int</span> nowl<span class="token punctuation">,</span> <span class="token keyword">int</span> nowr<span class="token punctuation">,</span> <span class="token keyword">int</span> L<span class="token punctuation">,</span> <span class="token keyword">int</span> R<span class="token punctuation">,</span> <span class="token keyword">int</span> x<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>L <span class="token operator">></span> R<span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token punctuation">;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>L <span class="token operator">&lt;=</span> nowl <span class="token operator">&amp;&amp;</span> nowr <span class="token operator">&lt;=</span> R<span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token function">tar</span><span class="token punctuation">(</span>o<span class="token punctuation">,</span> x<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> mid <span class="token operator">=</span> <span class="token punctuation">(</span>nowl <span class="token operator">+</span> nowr<span class="token punctuation">)</span> <span class="token operator">>></span> <span class="token number">1</span><span class="token punctuation">;</span>  <span class="token function">pushdown</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>L <span class="token operator">&lt;=</span> mid<span class="token punctuation">)</span> <span class="token function">update</span><span class="token punctuation">(</span><span class="token function">ls</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span><span class="token punctuation">,</span> nowl<span class="token punctuation">,</span> mid<span class="token punctuation">,</span> L<span class="token punctuation">,</span> R<span class="token punctuation">,</span> x<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>R  <span class="token operator">></span> mid<span class="token punctuation">)</span> <span class="token function">update</span><span class="token punctuation">(</span><span class="token function">rs</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span><span class="token punctuation">,</span> mid <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> nowr<span class="token punctuation">,</span> L<span class="token punctuation">,</span> R<span class="token punctuation">,</span> x<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">maintain</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    Node <span class="token function">query</span><span class="token punctuation">(</span><span class="token keyword">int</span> o<span class="token punctuation">,</span> <span class="token keyword">int</span> nowl<span class="token punctuation">,</span> <span class="token keyword">int</span> nowr<span class="token punctuation">,</span> <span class="token keyword">int</span> L<span class="token punctuation">,</span> <span class="token keyword">int</span> R<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>L <span class="token operator">&lt;=</span> nowl <span class="token operator">&amp;&amp;</span> nowr <span class="token operator">&lt;=</span> R<span class="token punctuation">)</span> <span class="token keyword">return</span> v<span class="token punctuation">[</span>o<span class="token punctuation">]</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> mid <span class="token operator">=</span> <span class="token punctuation">(</span>nowl <span class="token operator">+</span> nowr<span class="token punctuation">)</span> <span class="token operator">>></span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token function">pushdown</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span><span class="token punctuation">;</span>
        Node Ans<span class="token punctuation">;</span> Ans<span class="token punctuation">.</span>MIN <span class="token operator">=</span> INT_MAX<span class="token punctuation">;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>L <span class="token operator">&lt;=</span> mid<span class="token punctuation">)</span> Ans <span class="token operator">=</span> Ans <span class="token operator">+</span> <span class="token function">query</span><span class="token punctuation">(</span><span class="token function">ls</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span><span class="token punctuation">,</span> nowl<span class="token punctuation">,</span> mid<span class="token punctuation">,</span> L<span class="token punctuation">,</span> R<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>R  <span class="token operator">></span> mid<span class="token punctuation">)</span> Ans <span class="token operator">=</span> Ans <span class="token operator">+</span> <span class="token function">query</span><span class="token punctuation">(</span><span class="token function">rs</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span><span class="token punctuation">,</span> mid <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> nowr<span class="token punctuation">,</span> L<span class="token punctuation">,</span> R<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> Ans<span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">int</span> <span class="token function">query</span><span class="token punctuation">(</span><span class="token keyword">int</span> o<span class="token punctuation">,</span> <span class="token keyword">int</span> L<span class="token punctuation">,</span> <span class="token keyword">int</span> R<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        Node res <span class="token operator">=</span> <span class="token function">query</span><span class="token punctuation">(</span>o<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> n<span class="token punctuation">,</span> L<span class="token punctuation">,</span> R<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> res<span class="token punctuation">.</span>MIN <span class="token operator">==</span> <span class="token number">0</span> <span class="token operator">?</span> res<span class="token punctuation">.</span>sMIN <span class="token operator">:</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
<span class="token punctuation">&#125;</span>  <span class="token keyword">using</span> SegmentTree<span class="token operator">::</span>Groot<span class="token punctuation">;</span> <span class="token keyword">using</span> SegmentTree<span class="token operator">::</span>build<span class="token punctuation">;</span> <span class="token keyword">using</span> SegmentTree<span class="token operator">::</span>query<span class="token punctuation">;</span> <span class="token keyword">using</span> SegmentTree<span class="token operator">::</span>update<span class="token punctuation">;</span>
<span class="token keyword">namespace</span> Mon_Stack<span class="token punctuation">&#123;</span>
    <span class="token keyword">int</span> t0t <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span> t1t <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    pair<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token operator">></span> S0<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">,</span> S1<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token keyword">int</span> <span class="token function">work</span><span class="token punctuation">(</span><span class="token keyword">int</span> <span class="token operator">*</span>A<span class="token punctuation">,</span> <span class="token keyword">int</span> n<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">int</span> Ans <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> root <span class="token operator">=</span> <span class="token function">Groot</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">build</span><span class="token punctuation">(</span>root<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> n<span class="token punctuation">)</span><span class="token punctuation">;</span>
        S0<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">.</span>fir <span class="token operator">=</span> S1<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">.</span>fir <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
            <span class="token function">update</span><span class="token punctuation">(</span>root<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> n<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> i <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">while</span><span class="token punctuation">(</span>t0t <span class="token operator">!=</span> <span class="token number">0</span> <span class="token operator">&amp;&amp;</span> S0<span class="token punctuation">[</span>t0t<span class="token punctuation">]</span><span class="token punctuation">.</span>sec <span class="token operator">>=</span> A<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token function">update</span><span class="token punctuation">(</span>root<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> n<span class="token punctuation">,</span> S0<span class="token punctuation">[</span>t0t <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">.</span>fir <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> S0<span class="token punctuation">[</span>t0t<span class="token punctuation">]</span><span class="token punctuation">.</span>fir<span class="token punctuation">,</span>  S0<span class="token punctuation">[</span>t0t<span class="token punctuation">]</span><span class="token punctuation">.</span>sec<span class="token punctuation">)</span><span class="token punctuation">;</span> t0t<span class="token operator">--</span><span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
            <span class="token keyword">while</span><span class="token punctuation">(</span>t1t <span class="token operator">!=</span> <span class="token number">0</span> <span class="token operator">&amp;&amp;</span> S1<span class="token punctuation">[</span>t1t<span class="token punctuation">]</span><span class="token punctuation">.</span>sec <span class="token operator">&lt;=</span> A<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token function">update</span><span class="token punctuation">(</span>root<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> n<span class="token punctuation">,</span> S1<span class="token punctuation">[</span>t1t <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">.</span>fir <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> S1<span class="token punctuation">[</span>t1t<span class="token punctuation">]</span><span class="token punctuation">.</span>fir<span class="token punctuation">,</span> <span class="token operator">-</span>S1<span class="token punctuation">[</span>t1t<span class="token punctuation">]</span><span class="token punctuation">.</span>sec<span class="token punctuation">)</span><span class="token punctuation">;</span> t1t<span class="token operator">--</span><span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
            <span class="token function">update</span><span class="token punctuation">(</span>root<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> n<span class="token punctuation">,</span> S0<span class="token punctuation">[</span>t0t<span class="token punctuation">]</span><span class="token punctuation">.</span>fir <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> i<span class="token punctuation">,</span> <span class="token operator">-</span>A<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token function">update</span><span class="token punctuation">(</span>root<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> n<span class="token punctuation">,</span> S1<span class="token punctuation">[</span>t1t<span class="token punctuation">]</span><span class="token punctuation">.</span>fir <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> i<span class="token punctuation">,</span> A<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">int</span> t <span class="token operator">=</span> <span class="token function">query</span><span class="token punctuation">(</span>root<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> i<span class="token punctuation">)</span><span class="token punctuation">;</span>
            Ans <span class="token operator">+=</span> t<span class="token punctuation">;</span>
            S0<span class="token punctuation">[</span><span class="token operator">++</span>t0t<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">make_pair</span><span class="token punctuation">(</span>i<span class="token punctuation">,</span> A<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span> S1<span class="token punctuation">[</span><span class="token operator">++</span>t1t<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">make_pair</span><span class="token punctuation">(</span>i<span class="token punctuation">,</span> A<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
        <span class="token keyword">return</span> Ans<span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
<span class="token punctuation">&#125;</span> <span class="token keyword">using</span> Mon_Stack<span class="token operator">::</span>work<span class="token punctuation">;</span>
<span class="token keyword">signed</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    n <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token keyword">int</span> x <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> y <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> A<span class="token punctuation">[</span>x<span class="token punctuation">]</span> <span class="token operator">=</span> y<span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%lld\n"</span><span class="token punctuation">,</span> <span class="token function">work</span><span class="token punctuation">(</span>A<span class="token punctuation">,</span> n<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
</details>
<details class="note info"><summary><p>count(ZROI)</p>
</summary>
<pre class="line-numbers language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;climits></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cmath></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstring></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;algorithm></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token expression"><span class="token keyword">int</span> <span class="token keyword">long</span> <span class="token keyword">long</span> </span></span>
<span class="token keyword">const</span> <span class="token keyword">int</span> MOD <span class="token operator">=</span> <span class="token number">1e9</span> <span class="token operator">+</span> <span class="token number">7</span><span class="token punctuation">;</span>
<span class="token keyword">const</span> <span class="token keyword">int</span> _M <span class="token operator">=</span> <span class="token number">2e5</span> <span class="token operator">+</span> <span class="token number">100</span><span class="token punctuation">;</span>
<span class="token keyword">inline</span> <span class="token keyword">int</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token keyword">char</span> c <span class="token operator">=</span> <span class="token function">getchar</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">int</span> sign <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token keyword">int</span> x <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token keyword">while</span><span class="token punctuation">(</span>c <span class="token operator">></span> <span class="token string">'9'</span> <span class="token operator">||</span> c <span class="token operator">&lt;</span> <span class="token string">'0'</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token keyword">if</span><span class="token punctuation">(</span>c<span class="token operator">==</span><span class="token string">'-'</span><span class="token punctuation">)</span>sign <span class="token operator">=</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span> c <span class="token operator">=</span> <span class="token function">getchar</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">&#125;</span> <span class="token keyword">while</span><span class="token punctuation">(</span>c <span class="token operator">&lt;=</span> <span class="token string">'9'</span> <span class="token operator">&amp;&amp;</span> c <span class="token operator">>=</span> <span class="token string">'0'</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> x <span class="token operator">*=</span> <span class="token number">10</span><span class="token punctuation">;</span> x <span class="token operator">+=</span> c <span class="token operator">-</span> <span class="token string">'0'</span><span class="token punctuation">;</span> c <span class="token operator">=</span> <span class="token function">getchar</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">&#125;</span> <span class="token keyword">return</span> x <span class="token operator">*</span> sign<span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
<span class="token keyword">int</span> MAX<span class="token punctuation">,</span> m<span class="token punctuation">;</span>
<span class="token keyword">int</span> have<span class="token punctuation">[</span>_M<span class="token punctuation">]</span><span class="token punctuation">,</span> tht <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> none<span class="token punctuation">[</span>_M<span class="token punctuation">]</span><span class="token punctuation">,</span> tnt <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> d<span class="token punctuation">[</span>_M<span class="token punctuation">]</span><span class="token punctuation">,</span> tdt <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> 
<span class="token keyword">int</span> c<span class="token punctuation">[</span>_M<span class="token punctuation">]</span><span class="token punctuation">;</span><span class="token comment">//tct = tdt</span>
<span class="token keyword">bool</span> CanBe<span class="token punctuation">[</span>_M<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> ToL<span class="token punctuation">[</span>_M<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> ToR<span class="token punctuation">[</span>_M<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">void</span> <span class="token function">divide</span><span class="token punctuation">(</span><span class="token keyword">int</span> s<span class="token punctuation">,</span> <span class="token keyword">int</span> x<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">*</span> i <span class="token operator">&lt;=</span> x<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>x <span class="token operator">%</span> i <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span> d<span class="token punctuation">[</span><span class="token operator">++</span>tdt<span class="token punctuation">]</span> <span class="token operator">=</span> i<span class="token punctuation">,</span> c<span class="token punctuation">[</span>tdt<span class="token punctuation">]</span> <span class="token operator">=</span> s <span class="token operator">%</span> i<span class="token punctuation">;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>i <span class="token operator">*</span> i <span class="token operator">!=</span> x<span class="token punctuation">)</span> d<span class="token punctuation">[</span><span class="token operator">++</span>tdt<span class="token punctuation">]</span> <span class="token operator">=</span> x <span class="token operator">/</span> i<span class="token punctuation">,</span> c<span class="token punctuation">[</span>tdt<span class="token punctuation">]</span> <span class="token operator">=</span> s <span class="token operator">%</span> d<span class="token punctuation">[</span>tdt<span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> tdt<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> CanBe<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">signed</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">int</span> t<span class="token punctuation">;</span>
    MAX <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> m <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> m<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">int</span> type <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>type <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">)</span> have<span class="token punctuation">[</span><span class="token operator">++</span>tht<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">else</span>          none<span class="token punctuation">[</span><span class="token operator">++</span>tnt<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token function">sort</span><span class="token punctuation">(</span>have <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> have <span class="token operator">+</span> <span class="token number">1</span> <span class="token operator">+</span> tht<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token function">sort</span><span class="token punctuation">(</span>none <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> none <span class="token operator">+</span> <span class="token number">1</span> <span class="token operator">+</span> tnt<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">int</span> maxd <span class="token operator">=</span> INT_MAX<span class="token punctuation">,</span> Sta<span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">2</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> tht<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>maxd <span class="token operator">></span> have<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">-</span> have<span class="token punctuation">[</span>i <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            maxd <span class="token operator">=</span> have<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">-</span> have<span class="token punctuation">[</span>i <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
            Sta <span class="token operator">=</span> have<span class="token punctuation">[</span>i <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token function">divide</span><span class="token punctuation">(</span>Sta<span class="token punctuation">,</span> maxd<span class="token punctuation">)</span><span class="token punctuation">;</span>

    <span class="token comment">/* 公差 及 特征 检查   */</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> tht<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> j <span class="token operator">&lt;=</span> tdt<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span>CanBe<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token keyword">continue</span><span class="token punctuation">;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>have<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">%</span> d<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">!=</span> c<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span> CanBe<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">2</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> tht<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">int</span> D <span class="token operator">=</span> have<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">-</span> have<span class="token punctuation">[</span>i <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> j <span class="token operator">&lt;=</span> tdt<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span>CanBe<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token keyword">continue</span><span class="token punctuation">;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>D <span class="token operator">%</span> d<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">!=</span> <span class="token number">0</span><span class="token punctuation">)</span> CanBe<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    t <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> tdt<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span>CanBe<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token keyword">continue</span><span class="token punctuation">;</span>
        d<span class="token punctuation">[</span><span class="token operator">++</span>t<span class="token punctuation">]</span> <span class="token operator">=</span> d<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
        c<span class="token punctuation">[</span>  t<span class="token punctuation">]</span> <span class="token operator">=</span> c<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
        CanBe<span class="token punctuation">[</span>t<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span> tdt <span class="token operator">=</span> t<span class="token punctuation">;</span>
    <span class="token comment">/* 公差 及 特征 检查   完成*/</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> tdt<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> 
        <span class="token keyword">if</span><span class="token punctuation">(</span>CanBe<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
            ToL<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">(</span>c<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token number">0</span> <span class="token operator">?</span> d<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">:</span> c<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span>
            <span class="token keyword">int</span> t <span class="token operator">=</span> MAX <span class="token operator">%</span> d<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>t <span class="token operator">==</span> c<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> ToR<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> MAX <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>t  <span class="token operator">></span> c<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> ToR<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> MAX <span class="token operator">-</span> <span class="token punctuation">(</span>t <span class="token operator">-</span> c<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>t  <span class="token operator">&lt;</span> c<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> ToR<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> MAX <span class="token operator">-</span> d<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">+</span> <span class="token punctuation">(</span>c<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">-</span> t<span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    t <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> tdt<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span>CanBe<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token keyword">continue</span><span class="token punctuation">;</span>
        d<span class="token punctuation">[</span><span class="token operator">++</span>t<span class="token punctuation">]</span> <span class="token operator">=</span> d<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
        c<span class="token punctuation">[</span>  t<span class="token punctuation">]</span> <span class="token operator">=</span> c<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
        CanBe<span class="token punctuation">[</span>t<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span> tdt <span class="token operator">=</span> t<span class="token punctuation">;</span>
    <span class="token keyword">int</span> MINS <span class="token operator">=</span> have<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">,</span> MAXE <span class="token operator">=</span> have<span class="token punctuation">[</span>tht<span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> tnt<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">int</span> now <span class="token operator">=</span> none<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> j <span class="token operator">&lt;=</span> tdt<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span>CanBe<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token keyword">continue</span><span class="token punctuation">;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>now <span class="token operator">%</span> d<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">==</span> c<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                <span class="token keyword">if</span><span class="token punctuation">(</span>now <span class="token operator">&lt;</span> MINS<span class="token punctuation">)</span>
                    ToL<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">max</span><span class="token punctuation">(</span>ToL<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span> now<span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span>now <span class="token operator">></span> MAXE<span class="token punctuation">)</span>
                    ToR<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">min</span><span class="token punctuation">(</span>ToR<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span> now<span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token keyword">else</span> CanBe<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> tdt<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token keyword">if</span><span class="token punctuation">(</span>ToL<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">></span> MINS <span class="token operator">||</span> ToR<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">&lt;</span> MAXE<span class="token punctuation">)</span> CanBe<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token boolean">false</span><span class="token punctuation">;</span> <span class="token keyword">else</span> ToL<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">++</span><span class="token punctuation">,</span> ToR<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">--</span><span class="token punctuation">;</span>
    <span class="token comment">/* 非法数字存在性检查 */</span>
    <span class="token keyword">int</span> ans <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> tdt<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span>CanBe<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token keyword">continue</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> k <span class="token operator">=</span> <span class="token punctuation">(</span>  <span class="token punctuation">(</span>MINS <span class="token operator">-</span> ToL<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">/</span> d<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">*</span> <span class="token punctuation">(</span> <span class="token punctuation">(</span>ToR<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">-</span> MAXE<span class="token punctuation">)</span> <span class="token operator">/</span> d<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">;</span> <span class="token comment">// TODO;</span>
        ans <span class="token operator">=</span> <span class="token punctuation">(</span>ans <span class="token operator">+</span> k<span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%lld"</span><span class="token punctuation">,</span> ans<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
</details>
<details class="note info"><summary><p>A.20联赛集训day3 树上排列(维护15次方和hash)</p>
</summary>
<pre class="line-numbers language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;climits></span> </span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstring></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cmath></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;algorithm></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;vector></span></span>
<span class="token keyword">inline</span> <span class="token keyword">int</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token keyword">char</span> c <span class="token operator">=</span> <span class="token function">getchar</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">int</span> sign <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token keyword">int</span> x <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token keyword">while</span><span class="token punctuation">(</span>c <span class="token operator">></span> <span class="token string">'9'</span> <span class="token operator">||</span> c <span class="token operator">&lt;</span> <span class="token string">'0'</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token keyword">if</span><span class="token punctuation">(</span>c<span class="token operator">==</span><span class="token string">'-'</span><span class="token punctuation">)</span>sign <span class="token operator">=</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span> c <span class="token operator">=</span> <span class="token function">getchar</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">&#125;</span> <span class="token keyword">while</span><span class="token punctuation">(</span>c <span class="token operator">&lt;=</span> <span class="token string">'9'</span> <span class="token operator">&amp;&amp;</span> c <span class="token operator">>=</span> <span class="token string">'0'</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> x <span class="token operator">*=</span> <span class="token number">10</span><span class="token punctuation">;</span> x <span class="token operator">+=</span> c <span class="token operator">-</span> <span class="token string">'0'</span><span class="token punctuation">;</span> c <span class="token operator">=</span> <span class="token function">getchar</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">&#125;</span> <span class="token keyword">return</span> x <span class="token operator">*</span> sign<span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>
<span class="token keyword">const</span> <span class="token keyword">int</span> _ <span class="token operator">=</span> <span class="token number">6e5</span> <span class="token operator">+</span> <span class="token number">100</span><span class="token punctuation">;</span>
<span class="token keyword">const</span> <span class="token keyword">int</span> base <span class="token operator">=</span> <span class="token number">15</span><span class="token punctuation">;</span>
<span class="token keyword">const</span> <span class="token keyword">int</span> MOD <span class="token operator">=</span> <span class="token number">1020031005</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> SS<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> <span class="token function">pow</span><span class="token punctuation">(</span><span class="token keyword">int</span> a<span class="token punctuation">,</span> <span class="token keyword">int</span> b <span class="token operator">=</span> base<span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token keyword">int</span> ans <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token keyword">while</span><span class="token punctuation">(</span>b<span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token keyword">if</span><span class="token punctuation">(</span>b <span class="token operator">&amp;</span> <span class="token number">1</span><span class="token punctuation">)</span> ans <span class="token operator">=</span> <span class="token punctuation">(</span>ans <span class="token operator">*</span><span class="token number">1ll</span><span class="token operator">*</span> a<span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">;</span> a <span class="token operator">=</span> <span class="token punctuation">(</span>a <span class="token operator">*</span><span class="token number">1ll</span><span class="token operator">*</span> a<span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">;</span> b <span class="token operator">>>=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token punctuation">&#125;</span> <span class="token keyword">return</span> ans<span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>

<span class="token keyword">int</span> head<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> NodeVal<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">struct</span> <span class="token class-name">edges</span><span class="token punctuation">&#123;</span>
	<span class="token keyword">int</span> node<span class="token punctuation">;</span>
	<span class="token keyword">int</span> nxt<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>edge<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> tot <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token keyword">void</span> <span class="token function">add</span><span class="token punctuation">(</span><span class="token keyword">int</span> u<span class="token punctuation">,</span> <span class="token keyword">int</span> v<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
	tot<span class="token operator">++</span><span class="token punctuation">;</span>
	edge<span class="token punctuation">[</span>tot<span class="token punctuation">]</span><span class="token punctuation">.</span>node <span class="token operator">=</span> v<span class="token punctuation">;</span>
	edge<span class="token punctuation">[</span>tot<span class="token punctuation">]</span><span class="token punctuation">.</span>nxt  <span class="token operator">=</span> head<span class="token punctuation">[</span>u<span class="token punctuation">]</span><span class="token punctuation">;</span>
	head<span class="token punctuation">[</span>u<span class="token punctuation">]</span>        <span class="token operator">=</span> tot<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>

<span class="token keyword">int</span> n<span class="token punctuation">,</span> q<span class="token punctuation">;</span>
<span class="token keyword">int</span> dep<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">,</span> fa<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">,</span> dfn<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">,</span> rnk<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">,</span> top<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">,</span> son<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">,</span> si<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">,</span> dfc <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token keyword">void</span> <span class="token function">dfs0</span><span class="token punctuation">(</span><span class="token keyword">int</span> now<span class="token punctuation">,</span> <span class="token keyword">int</span> f<span class="token punctuation">,</span> <span class="token keyword">int</span> dp<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
	<span class="token keyword">int</span> <span class="token operator">&amp;</span>S <span class="token operator">=</span> si<span class="token punctuation">[</span>now<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token keyword">int</span> <span class="token operator">&amp;</span>Mid <span class="token operator">=</span> son<span class="token punctuation">[</span>now<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> fa<span class="token punctuation">[</span>now<span class="token punctuation">]</span> <span class="token operator">=</span> f<span class="token punctuation">;</span> dep<span class="token punctuation">[</span>now<span class="token punctuation">]</span> <span class="token operator">=</span> dp<span class="token punctuation">;</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> head<span class="token punctuation">[</span>now<span class="token punctuation">]</span><span class="token punctuation">;</span> i <span class="token punctuation">;</span> i <span class="token operator">=</span> edge<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>nxt<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
		<span class="token keyword">int</span> ex <span class="token operator">=</span> edge<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>node<span class="token punctuation">;</span> <span class="token keyword">if</span><span class="token punctuation">(</span>ex <span class="token operator">==</span> f<span class="token punctuation">)</span> <span class="token keyword">continue</span><span class="token punctuation">;</span>
		<span class="token function">dfs0</span><span class="token punctuation">(</span>ex<span class="token punctuation">,</span> now<span class="token punctuation">,</span> dp <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span> S <span class="token operator">+=</span> si<span class="token punctuation">[</span>ex<span class="token punctuation">]</span><span class="token punctuation">;</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span>si<span class="token punctuation">[</span>ex<span class="token punctuation">]</span> <span class="token operator">></span> si<span class="token punctuation">[</span>Mid<span class="token punctuation">]</span><span class="token punctuation">)</span> Mid <span class="token operator">=</span> ex<span class="token punctuation">;</span>
	<span class="token punctuation">&#125;</span> <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span>Mid<span class="token punctuation">)</span> Mid <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">void</span> <span class="token function">dfs1</span><span class="token punctuation">(</span><span class="token keyword">int</span> now<span class="token punctuation">,</span> <span class="token keyword">int</span> f<span class="token punctuation">,</span> <span class="token keyword">int</span> tp<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
	dfn<span class="token punctuation">[</span>now<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token operator">++</span>dfc<span class="token punctuation">;</span> rnk<span class="token punctuation">[</span>dfc<span class="token punctuation">]</span> <span class="token operator">=</span> now<span class="token punctuation">;</span>
	top<span class="token punctuation">[</span>now<span class="token punctuation">]</span> <span class="token operator">=</span> tp<span class="token punctuation">;</span>
	<span class="token keyword">if</span><span class="token punctuation">(</span>son<span class="token punctuation">[</span>now<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token function">dfs1</span><span class="token punctuation">(</span>son<span class="token punctuation">[</span>now<span class="token punctuation">]</span><span class="token punctuation">,</span> now<span class="token punctuation">,</span> tp<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> head<span class="token punctuation">[</span>now<span class="token punctuation">]</span><span class="token punctuation">;</span> i <span class="token punctuation">;</span> i <span class="token operator">=</span> edge<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>nxt<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
		<span class="token keyword">int</span> ex <span class="token operator">=</span> edge<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>node<span class="token punctuation">;</span> <span class="token keyword">if</span><span class="token punctuation">(</span>ex <span class="token operator">==</span> f <span class="token operator">||</span> ex <span class="token operator">==</span> son<span class="token punctuation">[</span>now<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token keyword">continue</span><span class="token punctuation">;</span>
		<span class="token function">dfs1</span><span class="token punctuation">(</span>ex<span class="token punctuation">,</span> now<span class="token punctuation">,</span> ex<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">&#125;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">void</span> <span class="token function">clear</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
	<span class="token function">memset</span><span class="token punctuation">(</span>head<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token keyword">sizeof</span><span class="token punctuation">(</span>head<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	dfn<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> rnk<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> si<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> top<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> fa<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> son<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
	tot <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
	dfc <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> 
<span class="token punctuation">&#125;</span>
<span class="token keyword">namespace</span> SegmentTree<span class="token punctuation">&#123;</span>
	<span class="token keyword">const</span> <span class="token keyword">int</span> _ <span class="token operator">=</span> <span class="token number">3e6</span> <span class="token operator">+</span> <span class="token number">100</span><span class="token punctuation">;</span>
	<span class="token keyword">int</span> tot <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
	<span class="token keyword">int</span> ch<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
	<span class="token keyword">int</span> v<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">;</span>
	<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token expression"><span class="token function">make</span> <span class="token punctuation">(</span>tot<span class="token operator">++</span><span class="token punctuation">,</span> ch<span class="token punctuation">[</span>tot<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> ch<span class="token punctuation">[</span>tot<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> v<span class="token punctuation">[</span>tot<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span> tot<span class="token punctuation">)</span><span class="token punctuation">;</span></span></span>
	<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token expression"><span class="token function">ls</span><span class="token punctuation">(</span>x<span class="token punctuation">)</span> <span class="token punctuation">(</span>ch<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span></span></span>
	<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token expression"><span class="token function">rs</span><span class="token punctuation">(</span>x<span class="token punctuation">)</span> <span class="token punctuation">(</span>ch<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span></span></span>
	<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token expression"><span class="token function">maintain</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span> <span class="token punctuation">(</span>v<span class="token punctuation">[</span>o<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">(</span>v<span class="token punctuation">[</span><span class="token function">ls</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span><span class="token punctuation">]</span> <span class="token operator">+</span><span class="token number">0ll</span><span class="token operator">+</span> v<span class="token punctuation">[</span><span class="token function">rs</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">%</span> MOD <span class="token punctuation">)</span></span></span>
	<span class="token keyword">void</span> <span class="token function">init_s</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> tot <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
	<span class="token keyword">int</span>  <span class="token function">Groot</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token keyword">return</span> make<span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
	<span class="token keyword">void</span> <span class="token function">build</span><span class="token punctuation">(</span><span class="token keyword">int</span> o<span class="token punctuation">,</span> <span class="token keyword">int</span> L<span class="token punctuation">,</span> <span class="token keyword">int</span> R<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span>L <span class="token operator">==</span> R<span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token punctuation">(</span><span class="token keyword">void</span><span class="token punctuation">)</span><span class="token punctuation">(</span>v<span class="token punctuation">[</span>o<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">pow</span><span class="token punctuation">(</span>NodeVal<span class="token punctuation">[</span>rnk<span class="token punctuation">[</span>L<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token keyword">int</span> mid <span class="token operator">=</span> <span class="token punctuation">(</span>L <span class="token operator">+</span> R<span class="token punctuation">)</span> <span class="token operator">>></span> <span class="token number">1</span><span class="token punctuation">;</span>
		<span class="token function">ls</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span> <span class="token operator">=</span> make<span class="token punctuation">;</span> <span class="token function">rs</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span> <span class="token operator">=</span> make<span class="token punctuation">;</span>
		<span class="token function">build</span><span class="token punctuation">(</span><span class="token function">ls</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span><span class="token punctuation">,</span> L<span class="token punctuation">,</span> mid<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token function">build</span><span class="token punctuation">(</span><span class="token function">rs</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span><span class="token punctuation">,</span> mid <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> R<span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token function">maintain</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">&#125;</span>
	<span class="token keyword">void</span> <span class="token function">update</span><span class="token punctuation">(</span><span class="token keyword">int</span> o<span class="token punctuation">,</span> <span class="token keyword">int</span> nowl<span class="token punctuation">,</span> <span class="token keyword">int</span> nowr<span class="token punctuation">,</span> <span class="token keyword">int</span> p<span class="token punctuation">,</span> <span class="token keyword">int</span> x<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span>nowl <span class="token operator">==</span> nowr<span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token punctuation">(</span><span class="token keyword">void</span><span class="token punctuation">)</span><span class="token punctuation">(</span>v<span class="token punctuation">[</span>o<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">pow</span><span class="token punctuation">(</span>x<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token keyword">int</span> mid <span class="token operator">=</span> <span class="token punctuation">(</span>nowl <span class="token operator">+</span> nowr<span class="token punctuation">)</span> <span class="token operator">>></span> <span class="token number">1</span><span class="token punctuation">;</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span>p <span class="token operator">&lt;=</span> mid<span class="token punctuation">)</span> <span class="token function">update</span><span class="token punctuation">(</span><span class="token function">ls</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span><span class="token punctuation">,</span> nowl<span class="token punctuation">,</span> mid<span class="token punctuation">,</span> p<span class="token punctuation">,</span> x<span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span>p  <span class="token operator">></span> mid<span class="token punctuation">)</span> <span class="token function">update</span><span class="token punctuation">(</span><span class="token function">rs</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span><span class="token punctuation">,</span> mid <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> nowr<span class="token punctuation">,</span> p<span class="token punctuation">,</span> x<span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token function">maintain</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">&#125;</span>
	<span class="token keyword">int</span> <span class="token function">query</span><span class="token punctuation">(</span><span class="token keyword">int</span> o<span class="token punctuation">,</span> <span class="token keyword">int</span> nowl<span class="token punctuation">,</span> <span class="token keyword">int</span> nowr<span class="token punctuation">,</span> <span class="token keyword">int</span> L<span class="token punctuation">,</span> <span class="token keyword">int</span> R<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span>L <span class="token operator">></span> R<span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span>L <span class="token operator">&lt;=</span> nowl <span class="token operator">&amp;&amp;</span> nowr <span class="token operator">&lt;=</span> R<span class="token punctuation">)</span> <span class="token keyword">return</span> v<span class="token punctuation">[</span>o<span class="token punctuation">]</span><span class="token punctuation">;</span>
		<span class="token keyword">int</span> mid <span class="token operator">=</span> <span class="token punctuation">(</span>nowl <span class="token operator">+</span> nowr<span class="token punctuation">)</span> <span class="token operator">>></span> <span class="token number">1</span><span class="token punctuation">;</span>
		<span class="token keyword">int</span> ans <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span>L <span class="token operator">&lt;=</span> mid<span class="token punctuation">)</span> ans <span class="token operator">=</span> <span class="token punctuation">(</span>ans <span class="token operator">+</span><span class="token number">0ll</span><span class="token operator">+</span> <span class="token function">query</span><span class="token punctuation">(</span><span class="token function">ls</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span><span class="token punctuation">,</span> nowl<span class="token punctuation">,</span> mid<span class="token punctuation">,</span> L<span class="token punctuation">,</span> R<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">;</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span>R  <span class="token operator">></span> mid<span class="token punctuation">)</span> ans <span class="token operator">=</span> <span class="token punctuation">(</span>ans <span class="token operator">+</span><span class="token number">0ll</span><span class="token operator">+</span> <span class="token function">query</span><span class="token punctuation">(</span><span class="token function">rs</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span><span class="token punctuation">,</span> mid <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> nowr<span class="token punctuation">,</span> L<span class="token punctuation">,</span> R<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">;</span>
		<span class="token keyword">return</span> ans<span class="token punctuation">;</span>
	<span class="token punctuation">&#125;</span>
<span class="token punctuation">&#125;</span> <span class="token keyword">using</span> SegmentTree<span class="token operator">::</span>Groot<span class="token punctuation">;</span> <span class="token keyword">using</span> SegmentTree<span class="token operator">::</span>init_s<span class="token punctuation">;</span> <span class="token keyword">using</span> SegmentTree<span class="token operator">::</span>build<span class="token punctuation">;</span> <span class="token keyword">using</span> SegmentTree<span class="token operator">::</span>update<span class="token punctuation">;</span> <span class="token keyword">using</span> SegmentTree<span class="token operator">::</span>query<span class="token punctuation">;</span>
<span class="token keyword">int</span> root <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> LCA<span class="token punctuation">;</span>
<span class="token keyword">int</span> <span class="token function">QueryOnPath</span><span class="token punctuation">(</span><span class="token keyword">int</span> x<span class="token punctuation">,</span> <span class="token keyword">int</span> y<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
	<span class="token keyword">int</span> ans <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
	<span class="token keyword">while</span><span class="token punctuation">(</span>top<span class="token punctuation">[</span>x<span class="token punctuation">]</span> <span class="token operator">!=</span> top<span class="token punctuation">[</span>y<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span>dep<span class="token punctuation">[</span>top<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">]</span> <span class="token operator">></span> dep<span class="token punctuation">[</span>top<span class="token punctuation">[</span>y<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token function">swap</span><span class="token punctuation">(</span>x<span class="token punctuation">,</span> y<span class="token punctuation">)</span><span class="token punctuation">;</span>
		ans <span class="token operator">=</span> <span class="token punctuation">(</span>ans <span class="token operator">+</span><span class="token number">0ll</span><span class="token operator">+</span> <span class="token function">query</span><span class="token punctuation">(</span>root<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> n<span class="token punctuation">,</span> dfn<span class="token punctuation">[</span>top<span class="token punctuation">[</span>y<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">,</span> dfn<span class="token punctuation">[</span>y<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">;</span>
		y <span class="token operator">=</span> fa<span class="token punctuation">[</span>top<span class="token punctuation">[</span>y<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
	<span class="token punctuation">&#125;</span>
	<span class="token keyword">if</span><span class="token punctuation">(</span>dep<span class="token punctuation">[</span>x<span class="token punctuation">]</span> <span class="token operator">&lt;</span> dep<span class="token punctuation">[</span>y<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token function">swap</span><span class="token punctuation">(</span>x<span class="token punctuation">,</span> y<span class="token punctuation">)</span><span class="token punctuation">;</span> LCA <span class="token operator">=</span> y<span class="token punctuation">;</span>
	ans <span class="token operator">=</span> <span class="token punctuation">(</span>ans <span class="token operator">+</span><span class="token number">0ll</span><span class="token operator">+</span> <span class="token function">query</span><span class="token punctuation">(</span>root<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> n<span class="token punctuation">,</span> dfn<span class="token punctuation">[</span>y<span class="token punctuation">]</span><span class="token punctuation">,</span> dfn<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">;</span> 
	<span class="token keyword">return</span> ans<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">void</span> <span class="token function">doit</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
	<span class="token function">clear</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	n <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> q <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> NodeVal<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span>  n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token keyword">int</span> u <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> v <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token function">add</span><span class="token punctuation">(</span>u<span class="token punctuation">,</span> v<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token function">add</span><span class="token punctuation">(</span>v<span class="token punctuation">,</span> u<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
	<span class="token function">dfs0</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token function">dfs1</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token function">init_s</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> root <span class="token operator">=</span> <span class="token function">Groot</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token function">build</span><span class="token punctuation">(</span>root<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> n<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">while</span><span class="token punctuation">(</span>q<span class="token operator">--</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
		<span class="token keyword">int</span> opt <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> x <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> y <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span>opt <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
			<span class="token keyword">int</span> r <span class="token operator">=</span> <span class="token function">QueryOnPath</span><span class="token punctuation">(</span>x<span class="token punctuation">,</span> y<span class="token punctuation">)</span><span class="token punctuation">;</span>
			<span class="token keyword">int</span> Len <span class="token operator">=</span> dep<span class="token punctuation">[</span>x<span class="token punctuation">]</span> <span class="token operator">+</span> dep<span class="token punctuation">[</span>y<span class="token punctuation">]</span> <span class="token operator">-</span> <span class="token punctuation">(</span>dep<span class="token punctuation">[</span>LCA<span class="token punctuation">]</span> <span class="token operator">&lt;&lt;</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span>
			<span class="token function">puts</span><span class="token punctuation">(</span>SS<span class="token punctuation">[</span>Len<span class="token punctuation">]</span> <span class="token operator">==</span> r <span class="token operator">?</span> <span class="token string">"Yes"</span> <span class="token operator">:</span> <span class="token string">"No"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token punctuation">&#125;</span> <span class="token keyword">else</span><span class="token punctuation">&#123;</span>
			<span class="token function">update</span><span class="token punctuation">(</span>root<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> n<span class="token punctuation">,</span> dfn<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">,</span> y<span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token punctuation">&#125;</span>
	<span class="token punctuation">&#125;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> <span class="token number">3e5</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> SS<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">(</span> SS<span class="token punctuation">[</span>i <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">+</span><span class="token number">0ll</span><span class="token operator">+</span> <span class="token function">pow</span><span class="token punctuation">(</span>i<span class="token punctuation">)</span> <span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">;</span>
	<span class="token keyword">int</span> T <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">while</span><span class="token punctuation">(</span>T<span class="token operator">--</span><span class="token punctuation">)</span> <span class="token function">doit</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
</details>

<h1 id="CF521E-Cycling-City"><a href="#CF521E-Cycling-City" class="headerlink" title="CF521E Cycling City"></a>CF521E Cycling City</h1><ul>
<li>给定一张 $n$ 个点 $m$ 条边的无向简单图。</li>
<li>问图中能否找到两个点，满足这两个点之间有至少三条完全不相交的简单路径。</li>
<li>$n,m \le 2 \times 10^5$，图不保证连通</li>
</ul>
<p>考虑生成树，对原图做一个生成树，考虑每个在生成树外的边，覆盖在树上，树上边被覆盖两次的，即为一种方案</p>
<p>由于树的拓扑结构比图要简单很多，直接思考图的生成树解决图内问题是一个常见思路。</p>
<h1 id="CF547D-Mike-and-Fish"><a href="#CF547D-Mike-and-Fish" class="headerlink" title="CF547D Mike and Fish"></a>CF547D Mike and Fish</h1><p><strong>待填</strong></p>

    </div>

    
    
    

    <footer class="post-footer">
          <div class="post-tags">
              <a target="_blank" href="//tags/好题/" rel="tag noopener"># 好题</a>
              <a target="_blank" href="//tags/题解/" rel="tag noopener"># 题解</a>
          </div>

        

          <div class="post-nav">
            <div class="post-nav-item">
                <a href="/2020/「比赛总结」洛谷-10-月赛/" rel="prev" title="「比赛总结」洛谷 10 月赛">
                  <i class="fa fa-chevron-left"></i> 「比赛总结」洛谷 10 月赛
                </a>
            </div>
            <div class="post-nav-item">
                <a href="/2020/「CSP-2020」退役有感/" rel="next" title="「CSP 2020」联赛有感">
                  「CSP 2020」联赛有感 <i class="fa fa-chevron-right"></i>
                </a>
            </div>
          </div>
    </footer>
  </article>
  
  
  



      
    <div class="comments" id="valine-comments"></div>

<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      const activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      const commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>

    </div>
  </main>

  <footer class="footer">
    <div class="footer-inner">
      

      

<div class="copyright">
  
  &copy; 2018 – 
  <span itemprop="copyrightYear">2021</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">舒雨墨</span>
</div>
<div class="wordcount">
  <span class="post-meta-item">
    <span class="post-meta-item-icon">
      <i class="fa fa-chart-line"></i>
    </span>
    <span title="站点总字数">319k</span>
  </span>
  <span class="post-meta-item">
    <span class="post-meta-item-icon">
      <i class="fa fa-coffee"></i>
    </span>
    <span title="站点阅读时长">4:50</span>
  </span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io/" class="theme-link" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.js.org/mist/" class="theme-link" rel="noopener" target="_blank">NexT.Mist</a> 强力驱动
  </div>

    </div>
  </footer>

  
  <script src="//cdn.jsdelivr.net/npm/animejs@3.2.0/lib/anime.min.js"></script>
  <script src="//cdn.jsdelivr.net/npm/@next-theme/pjax@0.4.0/pjax.min.js"></script>
<script src="/js/utils.js"></script><script src="/js/motion.js"></script><script src="/js/schemes/muse.js"></script><script src="/js/next-boot.js"></script>
  <script>
var pjax = new Pjax({
  selectors: [
    'head title',
    '.page-configurations',
    '.main-inner',
    '.post-toc-wrap',
    '.languages',
    '.pjax'
  ],
  analytics: false,
  cacheBust: false,
  scrollRestoration: false,
  scrollTo: !CONFIG.bookmark.enable
});

document.addEventListener('pjax:success', () => {
  pjax.executeScripts(document.querySelectorAll('script[data-pjax], .pjax script'));
  NexT.boot.refresh();
  // Define Motion Sequence & Bootstrap Motion.
  if (CONFIG.motion.enable) {
    NexT.motion.integrator
      .init()
      .add(NexT.motion.middleWares.subMenu)
      .add(NexT.motion.middleWares.postList)
      .bootstrap();
  }
  const hasTOC = document.querySelector('.post-toc');
  document.querySelector('.sidebar-inner').classList.toggle('sidebar-nav-active', hasTOC);
  document.querySelector(hasTOC ? '.sidebar-nav-toc' : '.sidebar-nav-overview').click();
  NexT.utils.updateSidebarPosition();
});
</script>


  
  <script data-pjax>
    (function(){
      var bp = document.createElement('script');
      var curProtocol = window.location.protocol.split(':')[0];
      bp.src = (curProtocol === 'https') ? 'https://zz.bdstatic.com/linksubmit/push.js' : 'http://push.zhanzhang.baidu.com/push.js';
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(bp, s);
    })();
  </script>




  <script src="/js/local-search.js"></script>












  






<script data-pjax>
  (function() {
    function leancloudSelector(url) {
      return document.getElementById(url).querySelector('.leancloud-visitors-count');
    }

    function addCount(Counter) {
      const visitors = document.querySelector('.leancloud_visitors');
      const url = decodeURI(visitors.id);
      const title = visitors.dataset.flagTitle;

      Counter('get', '/classes/Counter?where=' + encodeURIComponent(JSON.stringify({ url })))
        .then(response => response.json())
        .then(({ results }) => {
          if (results.length > 0) {
            const counter = results[0];
            leancloudSelector(url).innerText = counter.time + 1;
            Counter('put', '/classes/Counter/' + counter.objectId, { time: { '__op': 'Increment', 'amount': 1 } })
              .catch(error => {
                console.error('Failed to save visitor count', error);
              });
          } else {
              Counter('post', '/classes/Counter', { title, url, time: 1 })
                .then(response => response.json())
                .then(() => {
                  leancloudSelector(url).innerText = 1;
                })
                .catch(error => {
                  console.error('Failed to create', error);
                });
          }
        })
        .catch(error => {
          console.error('LeanCloud Counter Error', error);
        });
    }

    function showTime(Counter) {
      const visitors = document.querySelectorAll('.leancloud_visitors');
      const entries = [...visitors].map(element => {
        return decodeURI(element.id);
      });
      Counter('get', '/classes/Counter?where=' + encodeURIComponent(JSON.stringify({ url: { '$in': entries } })))
        .then(response => response.json())
        .then(({ results }) => {
          for (let url of entries) {
            const target = results.find(item => item.url === url);
            leancloudSelector(url).innerText = target ? target.time : 0;
          }
        })
        .catch(error => {
          console.error('LeanCloud Counter Error', error);
        });
    }

    const { app_id, app_key, server_url } = {"enable":true,"app_id":"Tw3wqSuCQwL4zK5pGCd6BkKa-gzGzoHsz","app_key":"lwlhdaYvNPPDLhBEGeUegbH6","server_url":null,"security":false};
    function fetchData(api_server) {
      const Counter = (method, url, data) => {
        return fetch(`${api_server}/1.1${url}`, {
          method,
          headers: {
            'X-LC-Id'     : app_id,
            'X-LC-Key'    : app_key,
            'Content-Type': 'application/json',
          },
          body: JSON.stringify(data)
        });
      };
      if (CONFIG.page.isPost) {
        if (location.hostname == '127.0.0.1' || location.hostname == 'localhost') ;
        else addCount(Counter);
      }
      if (document.querySelectorAll('.post-title-link').length >= 1 || document.querySelectorAll('.post-title').length >= 1) {
        showTime(Counter);
      }
    }

    const api_server = app_id.slice(-9) !== '-MdYXbMMI' ? server_url : `https://${app_id.slice(0, 8).toLowerCase()}.api.lncldglobal.com`;

    if (api_server) {
      fetchData(api_server);
    } else {
      fetch('https://app-router.leancloud.cn/2/route?appId=' + app_id)
        .then(response => response.json())
        .then(({ api_server }) => {
          fetchData('https://' + api_server);
        });
    }
  })();
</script>


    <div class="pjax">
  

  
      <script>
  if (typeof MathJax === 'undefined') {
    window.MathJax = {
      tex: {
        inlineMath: {'[+]': [['$', '$']]},
        tags: 'ams'
      },
      options: {
        renderActions: {
          findScript: [10, doc => {
            document.querySelectorAll('script[type^="math/tex"]').forEach(node => {
              const display = !!node.type.match(/; *mode=display/);
              const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display);
              const text = document.createTextNode('');
              node.parentNode.replaceChild(text, node);
              math.start = {node: text, delim: '', n: 0};
              math.end = {node: text, delim: '', n: 0};
              doc.math.push(math);
            });
          }, '', false],
          insertedScript: [200, () => {
            document.querySelectorAll('mjx-container').forEach(node => {
              const target = node.parentNode;
              if (target.nodeName.toLowerCase() === 'li') {
                target.parentNode.classList.add('has-jax');
              }
            });
          }, '', false]
        }
      }
    };
    const script = document.createElement('script');
    script.src = '//cdn.jsdelivr.net/npm/mathjax@3.1.0/es5/tex-mml-chtml.js';
    script.defer = true;
    document.head.appendChild(script);
  } else {
    MathJax.startup.document.state(0);
    MathJax.typesetClear();
    MathJax.texReset();
    MathJax.typeset();
  }
</script>

    

  
<script>
NexT.utils.loadComments('#valine-comments', () => {
  NexT.utils.getScript('//cdn.jsdelivr.net/npm/valine@1.4.14/dist/Valine.min.js', () => {
    new Valine(Object.assign({
      el  : '#valine-comments',
      path: "2020/「题单」IOI2020国家集训队作业-Part-1/",
    }, {"enable":true,"appId":"Tw3wqSuCQwL4zK5pGCd6BkKa-gzGzoHsz","appKey":"lwlhdaYvNPPDLhBEGeUegbH6","placeholder":"Just go go","avatar":"mm","meta":["nick","mail","link"],"pageSize":10,"lang":"zh-cn","visitor":false,"comment_count":true,"recordIP":true,"serverURLs":null,"enableQQ":true,"requiredFields":[]}
    ));
  }, window.Valine);
});
</script>

    </div>
</body>
</html>
